package com.banding.datastructure;

import java.util.function.BiConsumer;

public class HashTable<K, V> {

    private final int DEFAULT_INITIAL_CAPACITY = 16;
    private final double LOAD_FACTOR = 0.75;
    private Node<K, V>[] array;
    private int size = 0;

    public HashTable() {
        array = (Node<K, V>[]) new Node[DEFAULT_INITIAL_CAPACITY];
    }

    // 返回哈希表中的键值对个数
    public int size() {
        return size;
    }

    // 判断哈希表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 插入键值对
    public void put(K key, V value) {
        int index = hash(key, array.length);
        Node<K, V> head = array[index];
        Node<K, V> current = head;
        while (current != null) {
            if (current.key.equals(key)) {
                current.value = value;
                return;
            }
            current = current.next;
        }

        array[index] = new Node<>(key, value, head);
        size++;
        if ((double) size / array.length > LOAD_FACTOR) {
            grow();
        }
    }

    private void grow() {
        Node<K, V>[] newArray = new Node[array.length * 2];
        for (int i = 0; i < array.length; i++) {
            Node<K, V> node = array[i];
            while (node != null) {
                Node<K, V> next = node.next;

                int newIndex = hash(node.key, newArray.length);
                node.next = newArray[newIndex];
                newArray[newIndex] = node;

                node = next;
            }

        }
        array = newArray;
    }

    /**
     * 哈希函数,对key的哈希码进行取余运算
     *
     * @param key    键
     * @param length 数组长度
     * @return 哈希值，作为数组索引
     */
    private int hash(K key, int length) {
        return (key.hashCode() & Integer.MAX_VALUE) % length;
    }

    // 根据key获取对应value
    public V get(K key) {
        int index = hash(key, array.length);
        Node<K, V> node = array[index];
        Node<K, V> current = node;
        while (current != null) {
            if (current.key.equals(key)) {
                return current.value;
            }
            current = current.next;
        }
        return null;
    }

    /**
     * 删除指定key对应的键值对
     *
     * @param key 键
     * @return 若存在，则返回key对应的值，否则返回null
     */
    public V remove(K key) {
        int index = hash(key, array.length);
        Node<K, V> head = array[index];
        V result = null;
        if(head != null){
            if(head.key.equals(key)){
                result = head.value;
                array[index] = head.next;
                size--;
            }else{
                Node<K, V> pre = head;
                while (pre.next != null){
                    if(pre.next.key.equals(key)){
                        result = pre.next.value;
                        pre.next = pre.next.next;
                        size--;
                        break;
                    }
                    pre = pre.next;
                }
            }
        }
        return result;
    }

    // 遍历哈希表中的所有键值对
    public void forEach(BiConsumer<K,V> consumer) {
        for (int i = 0; i < array.length; i++) {
            Node<K, V> node = array[i];
            while (node != null){
                consumer.accept(node.key,node.value);
                node = node.next;
            }
        }
    }

    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> next;

        Node(K key, V value, Node<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }

        /**
         * 链表内容展示形式为[(k1:v1)->(k2:v2)->(k3:v3)->null]
         *
         * @return 链表所有元素
         */
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            Node<K, V> current = this;
            do {
                sb.append("(").append(current.key).append(":").append(current.value).append(")->");
                current = current.next;
            } while (current != null);
            sb.append("null]");
            return sb.toString();
        }
    }
}
